P1792 [国家集训队] 种树

题意

一个环上有 $n$ 个位置，第 $i$ 个位置种树可得美观度 $A_i$，相邻位置（含 $1$ 与 $n$） 不能同时种树。恰好种 $m$ 棵树，最大化美观度之和；不可能则输出 Error!。

关键观察

先看直接贪心为什么错：每次取当前美观度最大的位置并ban掉它两侧。 反例 4 7 8 9 中取 $m=2$，贪心会先拿 $9$ 再拿 $4$（或类似），而 $\{7,8\}$ 更优。 问题在于"取最大值"这个决策可能把更好的相邻组合排除了，所以需要反悔机制。

反悔贪心的核心（可解任意实数权值，包括负数）：

1. 把所有位置放进大根堆，并维护双向链表表示环上的前驱/后继。

2. 每次取出堆顶 $i$（局部最优），累加答案，然后不真正删掉 $i$， 而是把 $i$ 的左右两点 $l,r$ 删除，令 $i$ 的新权值为

   $$A_i^{\prime }=A_l+A_r-A_i$$

   并把 $i$ 重新压回堆中（链表上 $i$ 现在夹在 $l$ 的左边点和 $r$ 的右边点之间）。

3. 重复 $m$ 次。

为什么正确：若后续 $A_i^{\prime }$ 被选中，累计贡献为

$$A_i+(A_l+A_r-A_i)=A_l+A_r$$

即 $A_i$ 被"撤销"，等价于放弃 $i$ 而改选它的两个邻居——一次决策换成了另一次决策， 这正是反悔。又因为堆保证取出的 $i$ 不小于其在同一合法组合下可能被替换的值， 这种带交换的贪心逐步逼近最优解（本质上是"每次做一个局部最优的增广"）。

无解判定

环上最多能种 $\lfloor n/2\rfloor$ 棵（隔一个种一个），故 $m>\lfloor n/2\rfloor$ 时输出 Error!。

实现要点

• 环：pre[1]=n, nxt[n]=1。
• 堆中保留已删除位置会过期，弹出时用 vis[i] 惰性跳过。
• 合并时注意顺序：先取 l = pre[i], r = nxt[i] 与被删两点的外层点， 再让 i 接上 pre[l] 与 nxt[r]。
• 答案用 long long（$n\le 2\times {10}^5,|A_i|\le 1000$，绝对值上限约 $2\times {10}^8$， 但 long long 更稳妥）。

复杂度

时间 $O((n+m)\log n)$，空间 $O(n)$。

费用流版本（sol_mcmf.cpp）

反悔贪心不是凑出来的技巧，它就是下面这个费用流模型的模拟。

建模. 把位置 $i$ 想成一条边：环上相邻的两个位置之间取一条边，则 "选 $m$ 个互不相邻的位置"$⟺$"选 $m$ 条两两不共端点的边"，也就是大小为 $m$ 的 （最大权）匹配。匹配用最小费用最大流求：

弧	容量	费用	含义
$S\to L_v$	1	0	顶点 $v$ 最多被用一次
$L_v\to R_u$	1	$-A_i$	图上的边 $\{v,u\}$，即"在位置 $i$ 种树"
$R_u\to T$	1	0	同上

路径是二分图（按下标奇偶二染色），所以只连 $L_{\text{偶}}\to R_{\text{奇}}$； 推 $m$ 单位流量的最小费用取负即答案。环用"枚举 1 号种不种"化归成两条路径。

为什么贪心能 $O((n+m)\log n)$. 这条网络是特殊图，最短增广路很长一段时间里都是 "局部"的：一次增广沿着当前链走，把已选的 $i$ 换成它的两个邻居——正是 $A_l+A_r-A_i$ 这个反悔项。所以堆+双向链表那一版等价于对偶网络上做 successive shortest paths：每轮恰好一条增广路，流量（= 种的树数）恰好 $+1$， 而"退流边"就是反悔项。

取舍. 显式跑费用流是 $O(m\cdot E\log V)=O(mn\log n)$：$n=4000$ 约 $1.2$ s、 $n=8000$ 约 $5$ s，上限数据 $n=2\times {10}^5$ 会超时（几十倍到上千倍）， 但胜在模型直观、易于验证正确性（sol_mcmf.cpp 与本目录 sol.cpp 在随机对拍中完全一致）。交题请用 sol.cpp。

这题教了什么

"可反悔贪心 / 模拟费用流的退流"这一套想法的模板：用堆做贪心，用链表把"一次选择" 打包成"与它互斥的更优组合"重新投回堆，等价于给贪心一次买后悔药的机会。 与 P1484（线性版本）、BZOJ 1150 数据备份同源，是把交换论证变成数据结构操作的经典手法。